#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    bool isValid(string s)
    {
        stack<char> sk;
        int n = s.size();
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{')
            {
                sk.push(s[i]);
            }
            else
            {
                if (sk.empty()) return false;

                char top = sk.top();
                sk.pop();
                if (s[i] == ')' && top != '('
                    || s[i] == ']' && top != '['
                    || s[i] == '}' && top != '{')
                {
                    return false;
                }
            }
        }
        if (!sk.empty()) return false;

        return true;
    }
};

class MyStack {
public:
    MyStack()
    {}

    void push(int x)
    {
        if (!first.empty())
            first.push(x);
        else
            second.push(x);
    }

    int pop()
    {
        int tmp = 0;
        if (!first.empty())
        {
            while (!first.empty())
            {
                tmp = first.front();
                first.pop();
                if (!first.empty())
                {
                    second.push(tmp);
                }
            }
        }
        else
        {
            while (!second.empty())
            {
                tmp = second.front();
                second.pop();
                if (!second.empty())
                {
                    first.push(tmp);
                }
            }
        }
        return tmp;
    }

    int top()
    {
        if (!first.empty())
        {
            return first.back();
        }
        else
        {
            return second.back();
        }

    }

    bool empty()
    {
        return first.empty() && second.empty();
    }
private:
    queue<int> first;
    queue<int> second;

};